import heapq
import math


# -----------------------------------------------------------------------------
# 辅助类和函数 (学生通常不需要修改这部分)
# -----------------------------------------------------------------------------

class PriorityQueue:
    def __init__(self):
        self.items = []  # 初始化一个空列表作为堆

    def enqueue(self, item, priority):
        heapq.heappush(self.items, (priority, item))  # 添加元素及其优先级

    def dequeue(self):
        if not self.is_empty():
            return heapq.heappop(self.items)[1]  # 返回元素（忽略优先级）
        raise IndexError("无法从空优先队列出队")

    def is_empty(self):
        return len(self.items) == 0


def euclidean_distance(p1_coords, p2_coords):
    """计算两点之间的欧氏距离。p1_coords 和 p2_coords 是 (x,y) 元组。"""
    if p1_coords is None or p2_coords is None:
        return float('inf')
    return math.sqrt((p1_coords[0] - p2_coords[0]) ** 2 + (p1_coords[1] - p2_coords[1]) ** 2)


# -----------------------------------------------------------------------------
# 核心类定义 (学生需要在这部分进行修改)
# -----------------------------------------------------------------------------

class Vehicle:
    def __init__(self, id, location, capacity, initial_max_individual_time, time=0, distance_traveled=0):
        self.id = id
        self.location = location
        self.capacity = capacity
        self.time = time

        ### START STUDENT CODE HERE ###
        # 任务1: 为Vehicle类增加 max_individual_time_limit 和 total_distance_traveled 属性
        # 请将 max_individual_time_limit 初始化为传入的 initial_max_individual_time
        # 请将 total_distance_traveled 初始化为传入的 distance_traveled
        self.max_individual_time_limit = initial_max_individual_time  # 示例，学生需修改或确认
        self.total_distance_traveled = distance_traveled  # 示例，学生需修改或确认
        ### END STUDENT CODE HERE ###

    def __repr__(self):
        return (f"Vehicle(id={self.id}, loc={self.location}, cap={self.capacity}, "
                f"time={self.time:.2f}, dist_travel={self.total_distance_traveled:.2f}, "
                f"time_limit={self.max_individual_time_limit:.2f})")


class State:
    def __init__(self, vehicles_list, delivered_dict, current_max_time):
        self.vehicles = sorted(vehicles_list, key=lambda v: v.id)
        self.delivered = delivered_dict
        self.max_time = current_max_time

        ### START STUDENT CODE HERE ###
        # 任务2 (可选但推荐): 如果需要在State层面直接访问总距离，可以在这里计算并存储
        # 例如: self.total_system_distance = sum(v.total_distance_traveled for v in self.vehicles)
        self.total_system_distance = sum(v.total_distance_traveled for v in self.vehicles)  # 示例
        ### END STUDENT CODE HERE ###

    def __hash__(self):
        vehicle_details = tuple(
            (v.location, v.capacity, round(v.time, 5), round(v.total_distance_traveled, 5)) for v in self.vehicles)
        delivered_details = tuple(sorted(self.delivered.items()))
        return hash((vehicle_details, delivered_details, round(self.max_time, 5)))

    def __eq__(self, other):
        if not isinstance(other, State):
            return False
        if len(self.vehicles) != len(other.vehicles):
            return False

        vehicles_equal = all(
            s_v.id == o_v.id and
            s_v.location == o_v.location and
            s_v.capacity == o_v.capacity and
            round(s_v.time, 5) == round(o_v.time, 5) and
            round(s_v.total_distance_traveled, 5) == round(o_v.total_distance_traveled, 5)  # 确保比较距离
            for s_v, o_v in zip(self.vehicles, other.vehicles)
        )
        return (
                vehicles_equal and
                self.delivered == other.delivered and
                round(self.max_time, 5) == round(other.max_time, 5)
        )

    def __lt__(self, other):
        if not isinstance(other, State):
            return NotImplemented

        # 主要比较标准: max_time (越小越好)
        if round(self.max_time, 5) != round(other.max_time, 5):
            return round(self.max_time, 5) < round(other.max_time, 5)

        ### START STUDENT CODE HERE ###
        # 任务3: 实现次要比较标准 - 总行驶距离
        # 如果 self.max_time 与 other.max_time 近似相等，
        # 则比较 self.total_system_distance 和 other.total_system_distance。
        # 总行驶距离小的状态应该“更小”（优先级更高）。
        # (你需要确保 self.total_system_distance 和 other.total_system_distance 是可用的)
        if round(self.total_system_distance, 5) != round(other.total_system_distance, 5):
            return round(self.total_system_distance, 5) < round(other.total_system_distance, 5)  # 示例
        ### END STUDENT CODE HERE ###

        # 可选的第三比较标准: 总配送量 (越大越好)
        self_total_delivered = sum(self.delivered.values())
        other_total_delivered = sum(other.delivered.values())
        if self_total_delivered != other_total_delivered:
            return self_total_delivered > other_total_delivered

        return False  # 如果所有标准都相同

    def __repr__(self):
        return (f"State(max_time={self.max_time:.2f}, total_dist={self.total_system_distance:.2f}, "
                f"delivered={self.delivered}, vehicles={self.vehicles})")


class MultiVehiclePlanner:
    def __init__(self, nodes, graph, demands, vehicle_props):
        """
        vehicle_props: 列表，每个元素是一个元组 (capacity, max_individual_time_limit)
                       对应每辆车的容量和个体最大行驶时间。
        """
        self.nodes = nodes
        self.graph = graph
        self.demands = demands
        self.vehicle_properties = vehicle_props  # 例如 [(cap1, time_limit1), (cap2, time_limit2)]

        if self.graph:
            all_speeds = [speed for edges in self.graph.values() for _, _, speed in edges if speed > 0]
            self.min_speed = min(all_speeds) if all_speeds else 1
        else:
            self.min_speed = 1

    def initial_state(self):
        initial_vehicles = []
        for i, (capacity, max_time_limit) in enumerate(self.vehicle_properties, start=1):
            # 在创建Vehicle实例时传递 max_individual_time_limit
            vehicle = Vehicle(id=i, location=1, capacity=capacity, initial_max_individual_time=max_time_limit, time=0,
                              distance_traveled=0)
            initial_vehicles.append(vehicle)

        initial_delivered = {village_id: 0 for village_id in self.demands}
        return State(initial_vehicles, initial_delivered, 0)

    def is_goal(self, current_state):
        for village_id, required_demand in self.demands.items():
            if current_state.delivered.get(village_id, 0) < required_demand:
                return False
        return True

    def successors(self, current_state):
        possible_next_states = []
        for vehicle_idx_in_state_list, current_vehicle_from_state in enumerate(current_state.vehicles):
            if current_vehicle_from_state.location not in self.graph:
                continue

            for neighbor_id, distance, speed in self.graph[current_vehicle_from_state.location]:
                if speed <= 0: continue

                # --- 创建深拷贝 ---
                new_vehicles_list = []
                for v_orig in current_state.vehicles:
                    new_vehicles_list.append(
                        Vehicle(id=v_orig.id,
                                location=v_orig.location,
                                capacity=v_orig.capacity,
                                initial_max_individual_time=v_orig.max_individual_time_limit,  # 传递限制
                                time=v_orig.time,
                                distance_traveled=v_orig.total_distance_traveled)
                    )

                vehicle_to_move = new_vehicles_list[vehicle_idx_in_state_list]
                travel_time = distance / speed

                ### START STUDENT CODE HERE ###
                # 任务4: 在更新车辆状态前，检查移动是否会导致其超出个体时间限制
                # 如果 vehicle_to_move.time + travel_time > vehicle_to_move.max_individual_time_limit，
                # 则这个移动是无效的，应该 continue 跳过本次循环迭代，不生成此后继状态。
                if vehicle_to_move.time + travel_time > vehicle_to_move.max_individual_time_limit:
                    continue  # 示例

                # 任务5: 更新车辆的 total_distance_traveled 和 time
                vehicle_to_move.location = neighbor_id
                vehicle_to_move.time += travel_time
                vehicle_to_move.total_distance_traveled += distance  # 示例
                ### END STUDENT CODE HERE ###

                new_delivered_dict = current_state.delivered.copy()

                if neighbor_id == 1:  # 返回指挥中心补给
                    # 根据其原始属性找到车辆的初始容量
                    original_cap, _ = self.vehicle_properties[vehicle_to_move.id - 1]
                    vehicle_to_move.capacity = original_cap
                elif neighbor_id in self.demands and vehicle_to_move.capacity > 0:  # 到村庄配送
                    demand_at_target = self.demands[neighbor_id]
                    delivered_so_far = new_delivered_dict.get(neighbor_id, 0)
                    remaining_demand = demand_at_target - delivered_so_far
                    if remaining_demand > 0:
                        can_deliver = min(vehicle_to_move.capacity, remaining_demand)
                        vehicle_to_move.capacity -= can_deliver
                        new_delivered_dict[neighbor_id] += can_deliver

                new_max_overall_time = max(v.time for v in new_vehicles_list)
                possible_next_states.append(State(new_vehicles_list, new_delivered_dict, new_max_overall_time))
        possible_next_states.sort(key=lambda state: self.heuristic(state))
        return possible_next_states

    # 启发式函数
    def heuristic(self, current_state):
        # 1. 计算总剩余需求量
        total_remaining_demand = 0
        needy_village_ids = []  # 存储有需求的村庄的ID

        for village_id, required_demand in self.demands.items():
            delivered_so_far = current_state.delivered.get(village_id, 0)
            remaining = required_demand - delivered_so_far
            if remaining > 0:
                total_remaining_demand += remaining
                needy_village_ids.append(village_id)

        if total_remaining_demand == 0:
            return 0  # 所有需求已满足，未来成本为0

        # 2. 获取车队和图的一些关键参数
        max_one_vehicle_capacity = max(v[0] for v in self.vehicle_properties) if self.vehicle_properties else 1
        if max_one_vehicle_capacity <= 0:  # 容量必须为正
            return float('inf')
        # # 计算总容量
        # total_vehicles_cap = sum(p[0] for p in self.vehicle_properties) if self.vehicle_properties else 1
        # if total_remaining_demand > total_vehicles_cap:
        #     return float('inf')

        min_graph_speed = self.min_speed  # 在 __init__ 中已计算
        if min_graph_speed <= 0:
            return float('inf')  # 速度非正，无法移动

        # 3. 估算从指挥中心 (节点1) 到最远未满足需求村庄的（直线）距离
        max_dist_to_needy_village = 0
        depot_coords = self.nodes.get(1)  # 获取指挥中心坐标

        if depot_coords and needy_village_ids:
            current_max_dist = 0
            for v_id in needy_village_ids:
                village_coords = self.nodes.get(v_id)
                # 如果村庄坐标缺失，euclidean_distance会处理
                dist = euclidean_distance(depot_coords, village_coords)
                if dist > current_max_dist:
                    current_max_dist = dist
            max_dist_to_needy_village = current_max_dist
        elif not needy_village_ids:  # 没有需要物资的村庄了 (理论上已被 total_remaining_demand==0 捕获)
            return 0
        else:  # 没有指挥中心坐标，或没有需求村庄位置信息
            # 这种情况下，基于距离的启发式不适用。可以给一个基于需求的简单值。
            # 例如，假设平均距离为图中平均边长，或一个固定值。
            # 为了简单，如果无法计算有意义的距离，则启发式会偏低 (可能为0)，这仍然是可接受的。
            # 或者，可以遍历图找到一个平均或最大边长作为替代
            all_distances_in_graph = [d for edges_list in self.graph.values() for _, d, _ in edges_list if d > 0]
            max_dist_to_needy_village = max(all_distances_in_graph) if all_distances_in_graph else 10  # 备用值

        if max_dist_to_needy_village == 0 and total_remaining_demand > 0:
            # 如果距离为0但仍有需求（例如，所有需求都在指挥中心，这不太可能，但作为边界情况）
            # 此时时间成本应该很小，但不为0。设一个小的惩罚项。
            return total_remaining_demand / (max_one_vehicle_capacity * min_graph_speed + 1e-6)  # 避免除以零

        # 4. 计算启发值 - 至少需要的行程次数 * 单程最远时间 / 车辆数 (粗略并行)    
        num_full_loads_needed = math.ceil(total_remaining_demand / max_one_vehicle_capacity)

        # 单程最远时间估计
        time_for_one_furthest_trip = max_dist_to_needy_village / min_graph_speed

        # 启发值：总共需要的“最远单程”时间，再除以车辆数做并行估计
        h_value = (num_full_loads_needed * time_for_one_furthest_trip)
        if self.vehicle_properties and len(self.vehicle_properties) > 0:  # 两部分逻辑是否冗余？
            h_value /= len(self.vehicle_properties)

        return h_value

    # def heuristic(self, current_state):
    #     # 1. 计算总剩余需求量
    #     total_remaining_demand = 0
    #     needy_village_ids = []
    #     depot_coords = self.nodes.get(1)

    #     for village_id, required_demand in self.demands.items():
    #         delivered_so_far = current_state.delivered.get(village_id, 0)
    #         remaining = required_demand - delivered_so_far
    #         if remaining > 0:
    #             total_remaining_demand += remaining
    #             needy_village_ids.append(village_id)

    #     if total_remaining_demand == 0:
    #         return 0

    #     # 2. 获取关键参数
    #     try:
    #         max_capacity = max(v[0] for v in self.vehicle_properties)
    #         min_speed = self.min_speed
    #         num_vehicles = len(current_state.vehicles)
    #     except:
    #         return float('inf')

    #     if min_speed <= 0:
    #         min_speed = 0.1
    #     if num_vehicles == 0:
    #         return float('inf')

    #     # 3. 计算指挥中心到最远需求点的时间（使用欧氏距离）
    #     max_depot_to_village_time = 0
    #     if depot_coords and needy_village_ids:
    #         for v_id in needy_village_ids:
    #             village_coords = self.nodes.get(v_id)
    #             if village_coords:
    #                 dist = euclidean_distance(depot_coords, village_coords)
    #                 time_est = dist / min_speed
    #                 if time_est > max_depot_to_village_time:
    #                     max_depot_to_village_time = time_est

    #     # 4. 如果无法计算距离，使用图中最大距离的保守估计
    #     if max_depot_to_village_time <= 0:
    #         all_distances = [d for edges in self.graph.values() for _, d, _ in edges]
    #         max_distance = max(all_distances) if all_distances else 10.0
    #         max_depot_to_village_time = max_distance / min_speed

    #     # 5. 计算最少运输次数
    #     min_trips_needed = math.ceil(total_remaining_demand / max_capacity)

    #     # 6. 核心启发式值 - 往返时间
    #     base_h_value = min_trips_needed * 2 * max_depot_to_village_time

    #     # 7. 关键优化1: 车辆位置因子
    #     max_position_adjustment = 0
    #     if depot_coords:
    #         for vehicle in current_state.vehicles:
    #             if vehicle.location != 1:  # 车辆不在指挥中心
    #                 vehicle_coords = self.nodes.get(vehicle.location)
    #                 if vehicle_coords:
    #                     return_dist = euclidean_distance(vehicle_coords, depot_coords)
    #                     return_time = return_dist / min_speed
    #                     if return_time > max_position_adjustment:
    #                         max_position_adjustment = return_time

    #     # 8. 关键优化2: 并行效率因子
    #     # 根据车辆数量和需求计算并行效率
    #     parallel_factor = 1.0
    #     if num_vehicles > 1 and min_trips_needed > num_vehicles:
    #         # 有并行潜力时减少启发值
    #         parallel_factor = 0.7

    #     # 9. 关键优化3: 状态深度因子
    #     # 根据状态深度动态调整启发值
    #     depth_factor = 1.0
    #     if hasattr(current_state, 'depth'):
    #         # 状态越深，增加启发值以加速收敛
    #         depth_factor = min(1.5, 1.0 + current_state.depth * 0.01)

    #     # 10. 最终启发式值
    #     h_value = (base_h_value + max_position_adjustment) * parallel_factor * depth_factor

    #     return h_value

    def a_star(self):
        pq = PriorityQueue()
        start_node_state = self.initial_state()

        g_start = start_node_state.max_time
        h_start = self.heuristic(start_node_state)
        f_start = g_start + h_start

        pq.enqueue(start_node_state, f_start)
        came_from = {start_node_state: None}
        g_score = {start_node_state: g_start}

        explored_count = 0
        # 增加探索上限以应对可能更复杂的状态空间或次优启发式
        # 对于自动化测试，这个值可能需要根据测试算例的复杂度调整
        max_explored_limit = 20000

        while not pq.is_empty():
            current_s = pq.dequeue()
            explored_count += 1

            if current_s.max_time > g_score.get(current_s, float('inf')):
                continue  # Found a better path already

            if explored_count > max_explored_limit:
                print(f"探索达到上限 {max_explored_limit}，提前终止。")
                return None, float('inf'), explored_count

            if self.is_goal(current_s):
                total_path = []
                temp_current = current_s
                while temp_current is not None:
                    total_path.append(temp_current)
                    temp_current = came_from[temp_current]
                return total_path[::-1], current_s.max_time, explored_count

            for next_s in self.successors(current_s):
                tentative_g_next = next_s.max_time

                if tentative_g_next < g_score.get(next_s, float('inf')):
                    g_score[next_s] = tentative_g_next
                    came_from[next_s] = current_s
                    h_next = self.heuristic(next_s)
                    f_value_next = tentative_g_next + h_next
                    pq.enqueue(next_s, f_value_next)

        return None, float('inf'), explored_count


# -----------------------------------------------------------------------------
# 测试算例和主程序 (学生不应修改这部分，用于自动化测试)
# -----------------------------------------------------------------------------
def run_test_case(name, nodes, graph, demands, vehicle_props):
    print(f"\n--- 测试案例: {name} ---")
    planner = MultiVehiclePlanner(nodes, graph, demands, vehicle_props)

    start_time = time.time()
    final_path, total_time, num_explored = planner.a_star()
    end_time = time.time()
    execution_time = end_time - start_time

    if final_path:
        final_state = final_path[-1]
        total_dist_all_vehicles = sum(v.total_distance_traveled for v in final_state.vehicles)
        print(f"  🎉 解决方案找到!")
        print(f"    最慢车辆用时: {total_time:.2f}")
        print(f"    所有车辆总行驶距离: {total_dist_all_vehicles:.2f}")
        print(f"    共探索了 {num_explored} 个状态。")
        print(f"    路径长度 (状态数): {len(final_path)}")
        print(f"    运行时间: {execution_time:.4f} 秒")
        print("    最终状态车辆详情:")
        for v in final_state.vehicles:
            print(f"      {v}")
    else:
        print(f"  😥 未能找到解决方案。共探索了 {num_explored} 个状态。")
        print(f"    运行时间: {execution_time:.4f} 秒")


if __name__ == '__main__':
    import time

    # 测试案例 1: 基础案例，车辆时间限制宽松
    nodes_ex1 = {1: (0, 0), 2: (10, 0), 3: (0, 10)}
    graph_ex1 = {
        1: [(2, 10, 5), (3, 10, 5)],
        2: [(1, 10, 5), (3, 14.14, 2)],
        3: [(1, 10, 5), (2, 14.14, 2)]
    }
    demands_ex1 = {2: 10, 3: 5}
    # 车辆属性: [(capacity, max_individual_time_limit), ...]
    vehicle_props_ex1 = [(12, 100.0)]  # 1辆车, 容量12, 个体时间上限100
    run_test_case("基础案例 - 宽松时间限制", nodes_ex1, graph_ex1, demands_ex1, vehicle_props_ex1)

    # 测试案例 2: 车辆时间限制较紧
    vehicle_props_ex2 = [(12, 3.0)]  # 1辆车, 容量12, 个体时间上限3.0 (可能导致无解或不同解)
    run_test_case("时间限制较紧案例", nodes_ex1, graph_ex1, demands_ex1, vehicle_props_ex2)

    # 测试案例 3: 两辆车，不同限制和容量
    demands_ex3 = {2: 15, 3: 15}  # 需求增加
    vehicle_props_ex3 = [
        (10, 8.0),  # 车1: 容量10, 时间上限8
        (15, 10.0)  # 车2: 容量15, 时间上限10
    ]
    run_test_case("两辆车 - 不同属性", nodes_ex1, graph_ex1, demands_ex3, vehicle_props_ex3)

    # 测试案例 4: 稍微复杂一点的图和需求
    nodes_ex4 = {1: (0, 0), 2: (5, 0), 3: (10, 0), 4: (0, 5), 5: (5, 5)}
    graph_ex4 = {
        1: [(2, 5, 5), (4, 5, 5)],
        2: [(1, 5, 5), (3, 5, 5), (5, 7, 3)],
        3: [(2, 5, 5)],
        4: [(1, 5, 5), (5, 5, 5)],
        5: [(2, 7, 3), (4, 5, 5)]
    }
    demands_ex4 = {3: 10, 5: 12}
    vehicle_props_ex4 = [(15, 20.0)]
    run_test_case("稍复杂图和需求", nodes_ex4, graph_ex4, demands_ex4, vehicle_props_ex4)
    # 大规模数据测试
    nodes_data_large = {
        1: (0, 0), 2: (5, 149), 3: (118, 103), 4: (140, 132), 5: (102, 108),
        6: (90, 63), 7: (110, 140), 8: (18, 137), 9: (109, 130), 10: (100, 137),
        11: (142, 145), 12: (61, 12), 13: (40, 118), 14: (111, 10), 15: (147, 36),
        16: (123, 129), 17: (128, 81), 18: (13, 132), 19: (10, 80), 20: (70, 140),
        21: (28, 50), 22: (11, 138), 23: (111, 113), 24: (148, 108), 25: (93, 14),
        26: (149, 78), 27: (1, 104), 28: (102, 3), 29: (12, 13), 30: (81, 118),
        31: (110, 11), 32: (122, 117), 33: (136, 101), 34: (13, 101), 35: (141, 14)
    }
    graph_data_large = {
        1: [(2, 149.1, 6), (35, 141.0, 3), (29, 17.7, 7), (25, 94.0, 3), (21, 57.3, 7), (12, 62.2, 6)],
        2: [(1, 149.1, 6), (3, 120.0, 7), (8, 13.9, 7), (20, 65.2, 7), (22, 6.1, 6), (27, 45.1, 3)],
        3: [(2, 120.0, 7), (4, 30.4, 3), (5, 17.0, 5), (10, 37.6, 7), (16, 10.0, 6), (23, 7.1, 4)],
        4: [(3, 30.4, 3), (5, 41.8, 8), (7, 31.6, 5), (11, 13.3, 7), (16, 17.7, 5), (24, 24.7, 6)],
        5: [(3, 17.0, 5), (4, 41.8, 8), (6, 47.4, 8), (9, 23.0, 6), (17, 30.0, 7), (23, 10.2, 7)],
        6: [(5, 47.4, 8), (7, 54.1, 5), (12, 59.1, 7), (17, 38.0, 3), (19, 82.0, 4), (25, 49.2, 7)],
        7: [(4, 31.6, 5), (6, 54.1, 5), (8, 92.0, 5), (11, 32.0, 5), (16, 18.4, 6), (20, 40.0, 7)],
        8: [(2, 13.9, 7), (7, 92.0, 5), (9, 91.0, 5), (13, 28.6, 6), (18, 5.8, 5), (22, 7.1, 6)],
        9: [(5, 23.0, 6), (8, 91.0, 5), (10, 11.4, 6), (16, 13.0, 7), (23, 19.2, 5), (30, 30.5, 6)],
        10: [(3, 37.6, 7), (9, 11.4, 6), (11, 42.8, 7), (16, 26.4, 4), (20, 30.2, 3), (30, 24.2, 7)],
        11: [(4, 13.3, 7), (7, 32.0, 5), (10, 42.8, 7), (16, 19.9, 5), (20, 32.8, 7), (32, 33.9, 6)],
        12: [(1, 62.2, 6), (6, 59.1, 7), (14, 50.0, 6), (19, 53.1, 7), (21, 53.1, 6), (29, 49.0, 8)],
        13: [(8, 28.6, 6), (18, 27.0, 8), (19, 46.1, 5), (27, 40.8, 6), (30, 7.1, 6), (34, 27.9, 4)],
        14: [(12, 50.0, 6), (15, 43.2, 6), (17, 72.8, 5), (25, 18.4, 6), (28, 12.0, 7), (31, 0.0, 5)],
        15: [(14, 43.2, 6), (17, 50.1, 7), (26, 42.2, 4), (28, 51.1, 4), (31, 41.1, 8), (35, 23.3, 7)],
        16: [(3, 10.0, 6), (4, 17.7, 5), (7, 18.4, 6), (9, 13.0, 7), (10, 26.4, 4), (11, 19.9, 5)],  # Degree 6
        17: [(5, 30.0, 7), (6, 38.0, 3), (14, 72.8, 5), (15, 50.1, 7), (23, 34.0, 3), (26, 21.2, 7)],
        18: [(8, 5.8, 5), (13, 27.0, 8), (19, 52.0, 7), (22, 7.8, 6), (27, 13.3, 6), (34, 31.0, 3)],
        19: [(6, 82.0, 4), (12, 53.1, 7), (13, 46.1, 5), (18, 52.0, 7), (21, 34.5, 5), (27, 26.0, 7)],
        20: [(2, 65.2, 7), (7, 40.0, 7), (10, 30.2, 3), (11, 32.8, 7), (22, 59.0, 7), (30, 30.5, 3)],
        21: [(1, 57.3, 7), (12, 53.1, 6), (19, 34.5, 5), (29, 39.8, 7), (34, 53.2, 8)],
        22: [(2, 6.1, 6), (8, 7.1, 6), (18, 7.8, 6), (20, 59.0, 7), (27, 10.0, 6)],
        23: [(3, 7.1, 4), (5, 10.2, 7), (9, 19.2, 5), (17, 34.0, 3), (30, 31.0, 8), (32, 11.0, 5)],
        24: [(4, 24.7, 6), (26, 43.2, 3), (32, 29.7, 7), (33, 14.6, 6), (35, 94.6, 5)],
        25: [(1, 94.0, 3), (6, 49.2, 7), (14, 18.4, 6), (28, 9.9, 3), (31, 18.0, 7)],
        26: [(15, 42.2, 4), (17, 21.2, 7), (24, 43.2, 3), (28, 76.2, 7), (33, 26.0, 7), (35, 20.0, 6)],
        27: [(2, 45.1, 3), (13, 40.8, 6), (18, 13.3, 6), (19, 26.0, 7), (22, 10.0, 6), (34, 12.0, 8)],
        28: [(1, 102.0, 6), (14, 12.0, 7), (15, 51.1, 4), (25, 9.9, 3), (26, 76.2, 7), (31, 7.1, 6)],
        29: [(1, 17.7, 7), (12, 49.0, 8), (21, 39.8, 7), (34, 88.1, 5)],
        30: [(9, 30.5, 6), (10, 24.2, 7), (13, 7.1, 6), (20, 30.5, 3), (23, 31.0, 8), (32, 42.0, 6)],
        31: [(14, 0.0, 5), (15, 41.1, 8), (25, 18.0, 7), (28, 7.1, 6), (35, 6.1, 6)],
        32: [(11, 33.9, 6), (23, 11.0, 5), (24, 29.7, 7), (30, 42.0, 6), (33, 18.4, 8)],
        33: [(24, 14.6, 6), (26, 26.0, 7), (32, 18.4, 8), (35, 87.4, 5)],
        34: [(13, 27.9, 4), (18, 31.0, 3), (21, 53.2, 8), (27, 12.0, 8), (29, 88.1, 5)],
        35: [(1, 141.0, 3), (15, 23.3, 7), (24, 94.6, 5), (26, 20.0, 6), (31, 6.1, 6), (33, 87.4, 5)]
    }
    demands_data_large = {
        18: 58, 20: 38, 22: 36, 34: 22, 27: 52, 8: 35, 21: 41
    }
    vehicle_props_large = [
        (78, 153.4), (86, 139.2), (52, 229.5), (70, 169.8)
    ]
    run_test_case("大规模测例", nodes_data_large, graph_data_large, demands_data_large, vehicle_props_large)
